package com.atguigui.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 204.计数质数
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/6/30 9:00
 */
public class P204CountPrimes {
    public static void main(String[] args) {
        Solution solution = new P204CountPrimes().new Solution();
        // TO TEST
    }


    class Solution {
        /**
         * 枚举法求质数(超时)
         *
         * @param n
         * @return
         */
        public int countPrimes(int n) {

            int primesNums = 0;
            for (int i = 2; i < n; i++) {
                primesNums += isPrimes(i) ? 1 : 0;
            }
            return primesNums;
        }

        private boolean isPrimes(int n) {
            for (int i = 2; i * i <= n; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }


        /**
         * 埃氏筛
         *
         * @param n
         * @return
         */
        public int countPrimes1(int n) {

            boolean[] isPrime = new boolean[n];
            //都标记为true
            Arrays.fill(isPrime, true);
            int ans = 0;
            for (int i = 2; i < n; ++i) {
                if (isPrime[i]) {
                    //质数+1
                    ans += 1;
                    if ((long) i * i < n) {
                        // 对所有从 质数平方 开始质数的倍数的数 把数设置为合数
                        for (int j = i * i; j < n; j += i) {
                            isPrime[j] = false;
                        }
                    }
                }
            }

            return ans;
        }

        /**
         * 线性筛
         *
         * @param n
         * @return
         */
        public int countPrimes2(int n) {
            List<Integer> primes = new ArrayList<Integer>();
            int[] isPrime = new int[n];
            //都标记为true
            Arrays.fill(isPrime, 1);
            int ans = 0;
            for (int i = 2; i < n; ++i) {
                if (isPrime[i] == 1) {
                    //质数
                    primes.add(i);
                }
                for (int j = 0; j < primes.size() && i * primes.get(j) < n; ++j) {
                    isPrime[i * primes.get(j)] = 0;
                    if (i % primes.get(j) == 0) {
                        break;
                    }
                }
            }

            return primes.size();
        }

    }
}
